import java.util.Stack;

/**
 * @author yexiebao
 * @date 2025/5/15
 */
public class ReverseLinkedList {
    //用堆
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        //创建一个栈
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        head = stack.pop();
        curr = head;
        while(!stack.empty()){
             curr.next = stack.pop();
             curr = curr.next;
        }
        curr.next = null;
        return head;
    }
    //用双指针
    public ListNode reverseListByTwoPointers(ListNode head) {
        if(head == null){
            return null;
        }
        //虚拟头节点
        ListNode newHead = new ListNode();
        ListNode point = head;
        while(head!=null){
            head = head.next;
            point.next = newHead.next ;
            newHead.next = point;
            point  = head;
        }
        head = newHead.next;
        return head;
    }
}